package com.bupt.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import com.bupt.datastruct.TreeNode;


public class TreeSolution {
	/**
	 * leetCode 树初始化，由层次遍历结果得出
	 * @param arr
	 * @return
	 */
	public TreeNode leetCodeTreeSerialized(char[] arr){
		if(arr == null || arr.length == 0 || arr[0] == '#') return null;
		LinkedList<TreeNode> q = new LinkedList<TreeNode>();
		TreeNode root = new TreeNode(arr[0] - '0');
		q.offer(root);
		int k = 1;
		while(!q.isEmpty() && k < arr.length){
			int qSize = q.size();
			for(int i = 0; i < qSize; i++){
				TreeNode node = q.poll();
				TreeNode left = arr[k] == '#' ? null: new TreeNode(arr[k] - '0');
				node.left = left;
				if(left != null) {	
					q.offer(left);
				}
				k++;
				TreeNode right = arr[k] == '#' ? null: new TreeNode(arr[k] -'0');
				node.right = right;
				if(right != null){
					q.offer(right);
				}
				k++;
			}
		}
		return root;
	}
	/**
	 * 树的线序遍历非递归算法
	 * @param root
	 * @return
	 */
	public List<Integer> nonRecursivePreOrderTraverse(TreeNode root){
		List<Integer> results = new ArrayList<Integer>();
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		while(root != null || !stack.isEmpty()){
			if(root != null){
				results.add(root.val);
				stack.push(root);
				root = root.left;
			}else {
				TreeNode p = stack.pop();
				root = p.right;
			}
		}
		return results;
	}
	/**
	 * 树的中序遍历非递归算法
	 * @param root
	 * @return
	 */
	public List<Integer> nonRecursiveInOrderTraverse(TreeNode root){
		List<Integer> results = new ArrayList<Integer>();
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		while(root != null || !stack.isEmpty()){
			if( root != null){
				stack.push(root);
				root = root.left;
			}else{
				TreeNode p = stack.pop();
				results.add(p.val);
				root = p.right;
			}
		}
		return results;
	}
	/**
	 * 后序遍历二叉树非递归解法1
	 * @param root
	 * @return
	 */
	public List<Integer> nonRecursivePostOrderI(TreeNode root) {
		List<Integer> results = new ArrayList<Integer>();
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		TreeNode pre = null;
		if(root == null) return results;
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode cur = stack.peek();
			if(pre == null || pre.left == cur || pre.right == cur){
				if(cur.left != null){
					stack.push(cur.left);
				}else if(cur.right != null){
					stack.push(cur.right);
				}else{
					results.add(cur.val);
					stack.pop();
				}
			}else if(cur.left == pre && cur.right != null){
				stack.push(cur.right);
			}else{
				results.add(cur.val);
				stack.pop();
			}
			pre = cur;
		}
		return results;
	}
	/**
	 * 树的后续遍历非递归算法2
	 * @param root
	 * @return
	 */
	public List<Integer> nonRecursivePostOrderII(TreeNode root){
		List<Integer> results = new ArrayList<Integer>();
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		TreeNode pre = null,peekNode = null;
		while(root != null || !stack.isEmpty()){
			if(root != null){
				stack.push(root);
				root = root.left;
			}else{
				peekNode = stack.peek();
				if(peekNode.right != null && peekNode.right != pre){
					root = peekNode.right;
				}else{
					results.add(peekNode.val);
					stack.pop();
					pre = peekNode;
				}
			}
		}
		return results;
	}
	/**
	 * 树的分层遍历
	 * @param root
	 * @return
	 */
	public ArrayList<ArrayList<Integer>> levleOrder(TreeNode root){
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		while(root != null || !queue.isEmpty()){
			ArrayList<Integer> list = new ArrayList<Integer>();
			int levelSize = queue.size();
			for(int i = 0;i < levelSize;i++){
				TreeNode node = queue.poll();
				list.add(node.val);
				if(node.left != null){
					queue.add(node.left);
				}
				if(node.right != null){
					queue.add(node.right);
				}
			}
			res.add(list);
		}
		return res;
	}
	/**
	 * 获取从树根到某个节点的路径,非递归算法
	 * @param root
	 * @return
	 */
	public List<TreeNode> nonRecursiveGetPathFromRoot(TreeNode root,int target){
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		TreeNode pre = null;
		while(root != null || !stack.isEmpty()){
			if(root != null){
				stack.push(root);
				if(root.val == target) {
					return stack;
				}else{
					root = root.left;
				}
				
			}else{
				TreeNode peekNode = stack.peek();
				if(peekNode.right != null && peekNode.right != pre){
					root = peekNode.right;
				}else{
					stack.pop();
					pre = peekNode;
				}
			}
		}
		return stack;
	}
	/**
	 * 获取从跟节点到某一个节点的路径
	 * @param root
	 * @param target
	 * @return
	 */
	public List<TreeNode> recursiveGetPathFromRoot(TreeNode root,int target){
		LinkedList<TreeNode> res = new LinkedList<TreeNode>();
		getPathHelper(root,target,res);
		return res;
	}
	/**
	 * 递归体
	 * @param root
	 * @param target
	 * @param res
	 * @return
	 */
	public boolean getPathHelper(TreeNode root ,int target,LinkedList<TreeNode> res){
		if(root == null) return false;
		else {
			res.add(root);
			if(root.val == target) return true;
			if(getPathHelper(root.left,target,res)) return true;
			if(getPathHelper(root.right,target,res)) return true;
			res.removeLast();
			return false;
		}
	}
	/**
	 * 二叉树中两个节点的最近公共祖先
	 * @param root
	 * @param a
	 * @param b
	 * @return
	 */
	public TreeNode getRecentancestry(TreeNode root,int a,int b ){
		LinkedList<TreeNode> pathA = new LinkedList<TreeNode>();
		LinkedList<TreeNode> pathB = new LinkedList<TreeNode>();
		getPathHelper(root,a,pathA);
		getPathHelper(root,a,pathB);
		int i;
		for(i = 0; i < pathA.size() && i < pathB.size(); i++){
			if(pathA.get(i) != pathB.get(i)) break ;
		}
		return pathA.get(i-1);
	}
}
